import java.util.Arrays;

/**
 * 斐波那契查找算法：也类似于二分法查找算法，只不过改变了中间值为： mid = left + f(k - 1) - 1
 *      1.先创建一个斐波那契数列，用于寻找其中第一个大于或者等于， “查找数组长度” 值的下标。
 *         该下标值称为：k值；
 *         该下标对应的斐波那契值称为：f(k)值
 *      2.再根据 “f(k)值”的大小，将 “查找数组长度” 扩充至该值大小，扩充值都是以 “查找数组” 的最后一个值填充
 *          注意：查找数组 != 斐波那契数组（数列），查找数组可以是一个有序的随机数组，虽然随机，但必须有序
 *      3.再根据：mid = left + f(k - 1) - 1 公式求出 “查找数组的分隔值”，
 *          k: 参考上文 1.解释
 *          left:表示当前 “查找数组” 最左边的索引值。
 *              不一定为0，因为原始查找数组，会被分为两个子查找数组，子查找数组还会继续分割，直到找到需要找到的值
 *          mid:就是当前 “查找数组” 的分隔值的下标
 *      4.判断 查找数组中间值 arr[mid] 和 目标值 的关系，确定下一步策略：
 *          （1）如果目标值小于中间值，说明目标值在左区间。由于左区间长度为 F(n-1)，因此 n 应该更新为 n-1，然后再次执行 3、4 两步；
 *          （2）如果目标值大于中间值，说明目标值在右区间。由于右区间长度为 F(n-2)，因此 n 应该更新为 n-2，然后再次执行 3、4 两步；
 *          （3）如果目标值等于中间值，说明找到了目标值。但此时还需判别该目标值是原查找表中的元素还是填充元素：
 *          （4.1）如果是原查找表中的元素，直接返回索引；
 *          （4.2）如果是填充元素，则返回原查找表的最后一个元素的索引，即 arr.length-1。（因为扩展数组是以原查找表最后一个元素来填充，如果目标值是填充元素，则说明原查找表最后一个元素值就是目标值）
 *          注意：为什么目标值在左边区间，就将n更新为 n-1,目标值在右边，就将n更新为 n-2 ?
 *          这是计算机算法专家，研究出来的，这么做才会符合计算结果。
 */
public class FibonacciSearch {
    //定义一个值表示，斐波那契数列的最大长度
    public static int maxSize = 20;

    public static void main(String[] args) {
        int[] arr = {1,8,10,89,1000,1234};
        System.out.println(fibonacciSearch(arr, 10));
    }

    //创建斐波那契数列方法
    public static int[] fbn() {
        int[] f = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < maxSize - 1; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

    /**
     * 2.斐波那契查找算法:利用非递归方法
     *
     * @param arr 查找数组
     * @param key 查找的目标值
     * @return 存在就返回该值的下标，没有就返回 -1
     */
    public static int fibonacciSearch(int[] arr, int key) {
        int left = 0;//当前查找数组的最左边索引下标
        int right = arr.length - 1;//当前查找数组的最右边索引下标
        int mid = 0;//当前查找数组的分割值索引下标
        int k = 0;//斐波那契数列中第一个大于或者等于， “查找数组长度” 值的下标
        int[] f = fbn();//获取一个斐波那契数列

        //1.用于寻找斐波那契数列中,第一个大于或者等于 “查找数组长度” 值的下标
        while (f[k] < arr.length) {
            k++;
        }
        //2.扩充查找数组
        // 按照斐波那契数列中的元素长度拷贝一个查找表,多出来的位置，会以0填充，
        int[] temp = Arrays.copyOf(arr, f[k]);
        for (int i = arr.length; i < temp.length; i++) {
            //扩充值都是以 “查找数组” 的最后一个值填充
            temp[i] = arr[arr.length - 1];
        }
        //3.求出“查找数组”的分隔值，根据公式：mid = left + f(k-1)-1
        while (left <= right){
            mid = left + f[k - 1] - 1;
            if (key > temp[mid]) {
                //目标值若大于中间值
                left = mid +1;
                k -= 2;
            }else if (key < temp[mid]) {
                //若目标值小于中间值
                right = mid - 1;
                k--;
            }else {
                if (mid <= right) {
                    //如果是原查找表中的元素，直接返回索引；
                    return mid;
                }else {
                    //如果是填充元素，则返回原查找表的最后一个元素的索引，即 arr.length-1
                    return right;
                }
            }
        }
        return -1;//没有找到
    }

}
